package com.example.demo.sf;

import java.util.Iterator;

/**
 * 双向环形链表（带哨兵）
 */
public class DoublySignalLinkedListSentinel implements Iterable<Integer> {

    private Node sentinel = new Node(null,-1,null);

    public DoublySignalLinkedListSentinel() {
        sentinel.next = sentinel;
        sentinel.pre = sentinel;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node cur = sentinel.next;
            @Override
            public boolean hasNext() {
                return cur != sentinel;
            }

            @Override
            public Integer next() {
                int value = cur.value;
                cur = cur.next;
                return value;
            }
        };
    }

    private static class Node {
        private Node pre; // 上一个节点指针
        private int value; // 值
        private Node next; // 下一个节点指针

        public Node() {
        }

        public Node(Node pre, int value, Node next) {
            this.pre = pre;
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 添加元素到第一个位置
     */
    public void addFirst(int value) {
        Node node = new Node(sentinel, value, sentinel.next);
        sentinel.next.pre = node;
        sentinel.next = node;
    }
    /**
     * 添加元素到最后一个位置
     */
    public void addLast(int value) {
        Node node = new Node(sentinel.pre, value, sentinel);
        sentinel.pre = node;
        sentinel.pre.next = node;
    }

    /**
     * 删除第一个位置的元素
     */
    public void removeFirst() {
        // 首先找到第一个节点
        Node first = sentinel.next;
        if (first == sentinel) {
            System.out.println("链表为空");
            return;
        }
        // 找到第一个节点的下一个节点
        Node next = first.next;
        sentinel.next = next;
        next.pre = sentinel;
    }
    /**
     * 删除最后一个位置的元素
     */
    public void removeLast() {
        Node last = sentinel.pre;// 这是要删除的节点
        if (last == sentinel) {
            System.out.println("链表为空");
            return;
        }
        Node pre = last.pre;// 这是要删除的节点的上一个节点
        pre.next = sentinel;
        sentinel.pre = pre;
    }
    /**
     * 根据值查找节点
     * 从哨兵的next开始找，直到找到或者找到sentinel为止
     */
    public Node find(int value) {
        for (Node cur = sentinel.next; cur != sentinel; cur = cur.next) {
            if (cur.value == value) {
                return cur;
            }
        }
        return null;
    }

    /**
     * 根据值删除元素
     */
    public void remove(int value) {
        Node node = find(value);
        if (node == null) {
            System.out.println("没有该元素");
            return;
        }
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}
